package jleda.graph;

import jleda.tree.*;

public final class Dijkstra {
	private Dijkstra() {
		
	}
	
	public static int shortestPathLength( int[][] adjmat, int src, int dest ) {
		int[] dist = new int[adjmat.length];
		boolean[] visited = new boolean[adjmat.length];
		
		for( int i = 0; i < dist.length; i++ )
			dist[i] = Integer.MAX_VALUE >> 1;
		
		BinaryHeapMap<Integer,Integer> pq = new BinaryHeapMap<Integer,Integer>();
		dist[src] = 0;
		pq.insert( 0, src );
		
		while( !pq.isEmpty() ) {
			int node = pq.deleteMin();
			
			if( node == dest ) {
				return dist[dest];
			}
			
			if( !visited[node] ) {
				visited[node] = true;
				
				for( int i = 0; i < adjmat.length; i++ ) {
					if( !visited[i] && adjmat[node][i] != -1 && dist[node]+adjmat[node][i] < dist[i] ) {
						dist[i] = dist[node]+adjmat[node][i];
						pq.insert( dist[i], i );
					}
				}
			}
		}
		
		return -1;
	}
	
	public static int[] shortestPathLength( int[][] adjmat, int src ) {
		int[] dist = new int[adjmat.length];
		boolean[] visited = new boolean[adjmat.length];
		
		for( int i = 0; i < dist.length; i++ )
			dist[i] = Integer.MAX_VALUE >> 1;
		
		BinaryHeapMap<Integer,Integer> pq = new BinaryHeapMap<Integer,Integer>();
		int nleft = adjmat.length-1;
		dist[src] = 0;
		pq.insert( 0, src );
		
		while( !pq.isEmpty() ) {
			int node = pq.deleteMin();
			
			if( nleft == 0 ) {
				return dist;
			}
			
			if( !visited[node] ) {
				visited[node] = true;
				
				for( int i = 0; i < adjmat.length; i++ ) {
					if( !visited[i] && adjmat[node][i] != -1 && dist[node]+adjmat[node][i] < dist[i] ) {
						dist[i] = dist[node]+adjmat[node][i];
						pq.insert( dist[i], i );
					}
				}
			}
		}
		
		for( int i = 0; i < dist.length; i++ ) {
			if( dist[i] == Integer.MAX_VALUE >> 1 ) {
				dist[i] = -1;
			}
		}
		
		return dist;
	}
}
